// Project 5

#include <iostream>
#include <limits.h>
#include "d_except.h"
#include <fstream>
#include "d_matrix.h"
#include "graph.h"
#include <stack>

using namespace std;


struct mazeMap 
//Used to store the nodeId's and directions
//(go up/down/etc.) from start node to end node
{
      stack<int> nodePath;
      stack<string> direction;
};

class maze
{
   public:
      maze(ifstream &fin);

      int numRows(){return rows;};
      int numCols(){return cols;};

      void print(int,int,int,int);

      bool isLegal(int i, int j);
      bool isAdjacent(int row1, int col1, 
		      int row2, int col2);

      void setMap(int i, int j, int n);
      int getMap(int i, int j);
      void setReverseMap(int row, int col);
      int getReverseMapI(int n) const;
      int getReverseMapJ(int n) const;

      void mapMazeToGraph();

      void findPaths();
      string getDirection(int nodeSource, int nodeDest);
      

   private:
      //Members for mapping maze to graph
      void createNodes();
      void createEdges();
      void makeNewNode(int row, int col);
      void makeNewEdge(int, int, int, int);

      //Members for finding paths
      void findPathRecursive();
      bool dfsRecursive(int currentNodeId);
      void findPathNonRecursive();
      bool dfsNonRecursive();
      vector<int> getValidNeighbors(int currentNodeId);
      void fillInPathMap(stack<int> &nodePath);

      int rows; // number of rows in the maze
      int cols; // number of columns in the maze
      
      int currentRow; //Row of the current position
      int currentCol; //Column of the current position
      int goalRow; 
      int goalCol;

      matrix<bool> value;
      matrix<int> cellToNode; //Matrix that maps i/j vals to nodeId
      vector< vector<int> > nodeToCell; //Vector of 2-element vectors
      
      graph mazeGraph; 
      mazeMap pathMap; // Stores how to get to the goal

};

void maze::setMap(int i, int j, int n)
// Set mapping from maze cell (i,j) to graph node n. 
{
   cellToNode[i][j] = n;
}

int maze ::getMap(int i, int j)
// Return mapping of maze cell (i,j) in the graph.
{ 
   try 
   {
      isLegal(i, j);
   }
   catch (rangeError ex)
   {
      return -1;
   }
   
   if (!isLegal(i, j))
      return -1;
   
   return cellToNode[i][j];
}

void maze::setReverseMap(int row, int col)
//Push a vector containing row and col into nodeToCell
// Since the 2-element vector is always pushed into 
// nodeToCell, we can assume that the indeces of nodeToCell
// are the nodeId's (see getReverseMapI/J)
{
   vector<int> rowColVect;
   rowColVect.push_back(row);
   rowColVect.push_back(col);
   nodeToCell.push_back(rowColVect);
}

int maze ::getReverseMapI(int n) const
// Return reverse mapping of node n to it's maze i value.
{
   return nodeToCell[n][0];
}

int maze ::getReverseMapJ(int n) const
// Return reverse mapping of node n to it's maze j value.
{
   return nodeToCell[n][1];
}

maze::maze(ifstream &fin)
   :cellToNode(), nodeToCell(), mazeGraph()
    // Initializes a maze by reading values from fin.  Assumes that the
    // number of rows and columns indicated in the file are correct.
{
   fin >> rows;
   fin >> cols;

   char x;

   value.resize(rows,cols);
   for (int i = 0; i <= rows-1; i++)
      for (int j = 0; j <= cols-1; j++)
      {
	 fin >> x;
	 if (x == 'O')
	    value[i][j] = true;
	 else
	    value[i][j] = false;
      }

   cellToNode.resize(rows, cols);
}

void maze::print(int goalI, int goalJ, int currI, int currJ)
// Print out a maze, with the goal and current cells marked on the
// board.
{
   cout << endl;

   if (goalI < 0 || goalI >= numRows() || goalJ < 0 || goalJ > numCols())
      throw rangeError("Bad value in maze::print");

   if (currI < 0 || currI >= numRows() || currJ < 0 || currJ > numCols())
      throw rangeError("Bad value in maze::print");

   for (int i = 0; i <= numRows()-1; i++)
   {
      for (int j = 0; j <= numCols()-1; j++)
      {
	 if (i == goalI && j == goalJ)
	    cout << "*";
	 else
	    if (i == currI && j == currJ)
	       cout << "+";
	    else
	       if (value[i][j])
		  cout << " ";
	       else
		  cout << "X";	  
      }
      cout << endl;
   }
   cout << endl;
}

bool maze::isLegal(int i, int j)
// Return the value stored at the (i,j) entry in the maze, indicating
// whether it is legal to occupy cell (i,j).
{
   if (i < 0 || i >= numRows() || j < 0 || j >= numCols())
      throw rangeError("Bad value in maze::isLegal");

   return value[i][j];
}

bool maze::isAdjacent(int sourceRow, int sourceCol, 
                      int destRow, int destCol)
//Return true if the position given by (row1, col1)
// is adjacent to (row2, col2)
{
   //Return false for illegal coordinates (out-of-range)
   if (destRow < 0 || destCol < 0
       || destRow >= numRows() || destCol >= numCols())
      return false;

   //Return false if source cell is the destination cell
   if ((destRow == sourceRow && destCol == sourceCol))
      return false;

   //Finally, check if the source and destination cells are legal
   if (!isLegal(sourceRow, sourceCol) || !isLegal(destRow, destCol))
      return false;

   //The cells are adjacent. Return true
   else 
      return true;
} // end isAdjacent

void maze::createEdges()
//Creates one edge in mazeGraph for every pair, from
// source node to destination node.
{
   //for each row in the maze
   for (int sourceRow=0; sourceRow<numRows(); sourceRow++)

      //for each column in the maze
      for (int sourceCol=0; sourceCol<numCols(); sourceCol++)
      {
	 //Make a new edge for every adjacent cell
	 //in an up-down or left-right direction
	 int rowOffset[4] = {0, 0, 1, -1};
	 int colOffset[4] = {1, -1, 0, 0};

	 for (int idx=0; idx<4; idx++)
	 {
	    
	    if (isAdjacent(sourceRow, sourceCol,
			   sourceRow + rowOffset[idx], 
			   sourceCol + colOffset[idx]))
	       makeNewEdge(sourceRow, sourceCol, 
			   sourceRow + rowOffset[idx],
			   sourceCol + colOffset[idx]);
	 }
      }
} //end createEdges()

void maze::createNodes()
//Creates nodes in mazeGraph for every cell that is valid
{
   //foreach row
   for (int row = 0; row < numRows(); row++)

      //foreach col
      for (int col = 0; col < numCols(); col++)
      {

	 //make a new node if (row, col) is a legal move
	 if (isLegal(row, col))
	    makeNewNode(row, col);
      }
}

void maze::makeNewEdge(int sourceRow, int sourceCol, 
                       int destRow, int destCol)
//Create new edge between graph nodes given by 
// sourceRow/Col and destRow/Col
//Note that this will be called twice for every pair 
// of nodes, resulting in a bidirectional graph
{
   int sourceNode = getMap(sourceRow, sourceCol);
   int destNode = getMap(destRow, destCol);
   mazeGraph.addEdge(sourceNode, destNode);
}

void maze::makeNewNode(int row, int col)
//Make a new node, and associate the row, col
// to the nodeId 
{
   int nodeId = mazeGraph.addNode(1);
   setMap(row, col, nodeId);
   setReverseMap(row, col);
}

void maze::findPaths()
//Wrapper to findPathRecursive() and 
// findPathNonRecursive() as dictated in spec.
{
   cout << "Finding path with recursive implementation..." << endl;
   findPathRecursive();

   //clear pathMap
   while (!pathMap.nodePath.empty())
      pathMap.nodePath.pop();
   while (!pathMap.direction.empty())
      pathMap.direction.pop();

   cout << "Finding path with non-recursive implementation..." << endl;
   findPathNonRecursive();
}

void maze::findPathRecursive()
//Uses dfs recursively.  If no solutions are found, 
// print message.  After finding a solution, print each
// subsequent step from the start point
{
   int startNode = getMap(currentRow, currentCol);
   int goalNode = getMap(goalRow, goalCol);

   if ( !dfsRecursive(startNode) )
   {
      cout << "No solution" << endl;
      return;
   }
   
   //print each step for solving maze
   //nodes are storred in the nodePath stack
   while (!pathMap.nodePath.empty())
   {
      int currentNodeId = pathMap.nodePath.top();
      currentRow = getReverseMapI(currentNodeId);
      currentCol = getReverseMapJ(currentNodeId);
      pathMap.nodePath.pop();

      print(currentRow, currentCol, goalRow, goalCol);      
      if (!pathMap.direction.empty())
      {
	 string currentDir = pathMap.direction.top();
	 pathMap.direction.pop();
	 cout << currentDir << endl;
      }
   }
}

void maze::findPathNonRecursive()
//Uses dfs non-recursively.  If no solutions are found, 
// print message.  After finding a solution, print each
// subsequent step from the start point
//Note: in this case, the nodePath stack needs to be reversed
//      Hence, we get the directions as we reverse the nodePath
//      (both of which are done in fillInPathMap)
{
   currentRow = 0;
   currentCol = 0;

   if (!dfsNonRecursive())
   {
      cout << "No solution" << endl;
      return;
   }

   //Process the nodePath stack
   fillInPathMap(pathMap.nodePath);

   //Print each move to the goal...
   while (!pathMap.nodePath.empty())
   {
      int currentNodeId = pathMap.nodePath.top();
      currentRow = getReverseMapI(currentNodeId);
      currentCol = getReverseMapJ(currentNodeId);
      pathMap.nodePath.pop();

      print(currentRow, currentCol, goalRow, goalCol);      

      //Print a string telling which direction the next
      //  move will be
      if (!pathMap.direction.empty())
      {
	 string currentDir = pathMap.direction.top();
	 pathMap.direction.pop();
	 cout << currentDir << endl;
      }
   }

} // end findPathNonRecursive

void maze::fillInPathMap(stack<int> &nodePath)
//Reverse nodePath, and fill in the direction stack in pathMap
{
   stack<int> newStack;
   //reverse the nodePath, and fill in the direction stack
   while (!nodePath.empty())
   {
      int nodeDest = nodePath.top();
      nodePath.pop();
      newStack.push(nodeDest);
      if (!nodePath.empty())
      {
	 int nodeSource = nodePath.top();
	 string currentDir = getDirection(nodeSource, nodeDest);
	 pathMap.direction.push(currentDir);
      }
   }
   nodePath = newStack;
}

bool maze::dfsNonRecursive()
//As given in lecture, except we keep track of our
// path to the goal by pushing on node v when 
{
   stack<int> dfsStack;
   int startNode = getMap(currentRow, currentCol);
   int goalNode = getMap(goalRow, goalCol);
   //mark all nodes unvisited
   for (int idx=0; idx<mazeGraph.numNodes(); idx++)
      mazeGraph.unVisit(idx);

   //push start node on stack
   dfsStack.push(startNode);
   mazeGraph.visit(startNode);

   //While stack is not empty
   while (!dfsStack.empty())
   {
      int currentNode = dfsStack.top();
      if (pathMap.nodePath.empty() || 
	  currentNode != pathMap.nodePath.top())
	 pathMap.nodePath.push(currentNode);

      //check if we found the goal
      if (currentNode == goalNode)
	 return true;

      //If the current node has unvisited neighbors w...
      vector<int> neighborVect = getValidNeighbors(currentNode);
      if (neighborVect.size() > 0)
	 for (int idx = 0; idx < neighborVect.size(); idx++)
	 {
	    int w = neighborVect[idx];
	    //mark w as visited and push on stack
	    mazeGraph.visit(w);
	    dfsStack.push(w);
	 }
      else
      {
	 //Pop the dfsStack AND the nodePath stack
	 pathMap.nodePath.pop();
	 dfsStack.pop();
      }
   }

   //We only get here when there is no solution
   return false;

} //end dfsNonRecursive

string maze::getDirection(int currentNodeId, int neighborNodeId)
//Return the direction from currentNode to neighborNodeId
// ie - "Go up" "Go right" etc.
// We can assume that currentNodeId != neighborNodeId
{
   stack<int> direction;
   int currentRow = getReverseMapI(currentNodeId);
   int currentCol = getReverseMapJ(currentNodeId);
   int neighborRow = getReverseMapI(neighborNodeId);
   int neighborCol = getReverseMapJ(neighborNodeId);

   int rowOffset = neighborRow - currentRow;
   int colOffset = neighborCol - currentCol;

   switch (rowOffset)
   {
      case 1:
	 return "Go down";
      case -1:
	 return "Go up";
   }

   switch (colOffset)
   {
      case 1:
	 return "Go right";
      case -1:
	 return "Go left";
   }	 

} // end getDirection


bool maze::dfsRecursive(int currentNodeId)
//As shown in class, except bool to immediately unwind
// after finding a solution
{
   //mark the currentNodeId as visited
   mazeGraph.visit(currentNodeId);
   int goalNodeId = getMap(goalRow, goalCol);

   //check if we found the goal
   if ( currentNodeId == goalNodeId )
   {
      pathMap.nodePath.push(currentNodeId);
      return true;
   }

   vector<int> neighborVect = getValidNeighbors(currentNodeId);

   //For each neighboring node that is not visited
   for (int idx = 0; idx<neighborVect.size(); idx++)
   {
      int neighborNodeId = neighborVect[idx];

      if (dfsRecursive(neighborNodeId) )
      {
	 //In this block the currentNodeId is part of the
	 // path from start to end.  Store it and the direction
	 // to the next node in pathMap
	 string currentDir = getDirection(currentNodeId, 
					  pathMap.nodePath.top());
	 pathMap.direction.push(currentDir);
	 pathMap.nodePath.push(currentNodeId);
	 return true;
      }
   }

   return false;
} // end dfsRecursive()

vector<int> maze::getValidNeighbors(int currentNodeId) 
//Return neighbors of currentNodeId that are not visited
{
   int currentNodeRow = getReverseMapI(currentNodeId);
   int currentNodeCol = getReverseMapJ(currentNodeId);

   vector<int> adjNodes;
   
   //Keep all possible left,right,top,bottom offsets
   int rowOffset[4] = {0, 0, 1, -1};
   int colOffset[4] = {1, -1, 0, 0};

   //Foreach possible direction
   for (int idx=0; idx<4; idx++)
   {
      int adjNodeId = getMap(currentNodeRow + rowOffset[idx],
			     currentNodeCol + colOffset[idx]);
      if ( adjNodeId != -1 && !mazeGraph.isVisited(adjNodeId) )
	 adjNodes.push_back(adjNodeId);
   }

   return adjNodes;

} //end getValidNeighbors


void maze::mapMazeToGraph()
// Create the mazeGraph that represents the legal moves in the maze m.
{
   //Create the graph
   createNodes();
   createEdges();

   //Declare the start as upper left cell
   currentRow = 0;
   currentCol = 0;
   //... and the goal as lower right cell
   goalRow = numRows()-1;
   goalCol = numCols()-1;
}

int main(int argc, char* argv[])
{
   char x;
   ifstream fin;
   
   // Read the maze from the file.
   string fileName = (argc == 2) ? argv[1] : "maze.txt";

   fin.open(fileName.c_str());
   if (!fin)
   {
      cerr << "Cannot open " << fileName << endl;
      return (1);
   }

   try
   {
      while (fin && fin.peek() != 'Z')
      {
	 maze m(fin);
	 m.mapMazeToGraph();
	 m.findPaths();
      }
   }
   catch (indexRangeError &ex) 
   { 
      cout << ex.what() << endl; return (1);
   }
   catch (rangeError &ex)
   {
      cout << ex.what() << endl; return (1);
   }
}
